翻訳と辞書 Words near each other ・ Pillager Band of Chippewa Indians ・ Pillager, Minnesota ・ Pillai ・ Pillai (community) ・ Pillai (Nair title) ・ Pillai (surname) ・ Pillai Lokacharya ・ Pillai Nila ・ Pillai Nila (TV series) ・ Pillai prime ・ Pilina ・ Pilina solarium ・ Pilina unguis ・ Pilinella ・ Piling Bay ・ Piling-up lemma ・ Piliny ・ Piliny culture ・ Piliocalyx ・ Pilioniai ・ Pilioritikos ・ Piliostigma ・ Piliostigma thonningii ・ Pilip Ballach Ó Duibhgeannáin ・ Pilip Vaitsiakhovich ・ Pilipalpinae ・ Pilipectus ・ Pilipectus taiwanus ・ Pilipili ・ Pilipinas Basketball Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Piling-up lemma ： ウィキペディア英語版 Piling-up lemma In cryptanalysis, the piling-up lemma is a principle used in linear cryptanalysis to construct linear approximation to the action of block ciphers. It was introduced by Mitsuru Matsui (1993) as an analytical tool for linear cryptanalysis. ==Theory== The piling-up lemma allows the cryptanalyst to determine the probability that the equality: :$X\_1\backslash oplus\; X\_2\backslash oplus\backslash cdots\backslash oplus\; X\_n=0$ holds, where the ''X'' 's are binary variables (that is, bits: either 0 or 1). Let ''P''(A) denote "the probability that A is true". If it equals one, A is certain to happen, and if it equals zero, A cannot happen. First of all, we consider the piling-up lemma for two binary variables, where $P(X\_1\; =\; 0)=p\_1$ and $P(X\_2\; =\; 0)=p\_2$. Now, we consider: :$P(X\_1\; \backslash oplus\; X\_2\; =\; 0)$ Due to the properties of the xor operation, this is equivalent to :$P(X\_1=X\_2)$ ''X''1 = ''X''2 = 0 and ''X''1 = ''X''2 = 1 are mutually exclusive events, so we can say :$P(X\_1=X\_2)=P(X\_1=X\_2=0)\; +\; P(X\_1=X\_2=1)=P(X\_1=0,\; X\_2=0)\; +\; P(X\_1=1,\; X\_2=1)$ Now, we must make the central assumption of the piling-up lemma: the binary variables we are dealing with are independent; that is, the state of one has no effect on the state of any of the others. Thus we can expand the probability function as follows: Now we express the probabilities ''p''1 and ''p''2 as ½ + ε1 and ½ + ε2, where the ε's are the probability biases — the amount the probability deviates from ½. Thus the probability bias ε1,2 for the XOR sum above is 2ε1ε2. This formula can be extended to more ''X'' 's as follows: :$P(X\_1\backslash oplus\; X\_2\backslash oplus\backslash cdots\backslash oplus\; X\_n=0)=1/2+2^\backslash prod\_^n\; \backslash epsilon\_i$ Note that if any of the ε's is zero; that is, one of the binary variables is unbiased, the entire probability function will be unbiased — equal to ½. A related slightly different definition of the bias is $\backslash epsilon\_i\; =\; P(X\_i=1)\; -\; P(X\_i=0),$ in fact minus two times the previous value. The advantage is that now with $\backslash varepsilon\_=\; P(X\_1\backslash oplus\; X\_2\backslash oplus\backslash cdots\backslash oplus\; X\_n=1)-\; P(X\_1\backslash oplus\; X\_2\backslash oplus\backslash cdots\backslash oplus\; X\_n=0)$ we have :$\backslash varepsilon\_=(-1)^\backslash prod\_^n\; \backslash varepsilon\_i,$ adding random variables amounts to multiplying their (2nd definition) biases. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Piling-up lemma」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.